package com.clps.algorithm.chapter05.最近最少使用缓存;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private  ListNode head;
    private  ListNode tail;
    private Map<Integer,ListNode> map;
    int capacity;

    public LRUCache(int cap) {
        map = new HashMap<>();
        head = new ListNode(-1,-1);
        tail.next = tail;
        tail.prev = head;
        capacity = cap;
    }

    public  int get(int key){
        ListNode node = map.get(key);
        if(node == null){
            return  -1;
        }
        moveToTail(node,node.value);
        return  node.value;
    }

    public  void  put(int key,int value){
        if(map.containsKey(key)){
            moveToTail(map.get(key),value);
        }else{
            if(map.size() == capacity){
                ListNode toBeDeleted = head.next;
                deleteNode(toBeDeleted);
                map.remove(toBeDeleted.key);
            }

            ListNode node = new ListNode(key, value);
            inserToTail(node);
            map.put(key,node);
        }
    }

    private void inserToTail(ListNode node) {
        tail.prev.next= node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    private void deleteNode(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }


    private void moveToTail(ListNode node, int newValue) {
        deleteNode(node);
        node.value = newValue;
        inserToTail(node);
    }
}


class ListNode{
    public int key;
    public  int value;
    public  ListNode next;
    public  ListNode prev;

    public ListNode(int k,int v) {
     key= k;
     value = v;

    }
}
